package priority_queue

import (
	"fmt"
	"sync"
)

type PriorityQueue struct {
	data  []any               //动态数组
	len   uint64              //实际使用长度
	cap   uint64              //实际占用的空间的容量
	cmp   func(any, any) bool //该优先队列的比较器
	mutex sync.Mutex          //并发控制锁
}

func NewQueue(cmp func(any, any) bool) (pq *PriorityQueue) {
	//比较器为nil时后续的增删将会去寻找默认比较器
	return &PriorityQueue{
		data:  make([]interface{}, 1, 1),
		len:   0,
		cap:   1,
		cmp:   cmp,
		mutex: sync.Mutex{},
	}
}

// Push 推送
func (pq *PriorityQueue) Push(e any) {
	if pq.len != 0 {
		pq.len++
		pq.data = append([]any{e}, pq.data...)
		var i uint64
		var this any
		for i = 0; i < pq.len-1; i++ {
			if pq.cmp(pq.data[i], pq.data[i+1]) {
				// 交换
				this = pq.data[i]
				pq.data[i] = pq.data[i+1]
				pq.data[i+1] = this
			}
		}
	} else {
		pq.len++
		pq.data = []any{e}
	}
}

// Empty 判断是否为空
func (pq *PriorityQueue) Empty() bool {
	return pq.len == 0
}

// Pop 取队列头
func (pq *PriorityQueue) Pop() (p any) {
	p = pq.data[0]
	pq.data = pq.data[1:]
	pq.len--
	return
}

// Show 取队列头
func (pq *PriorityQueue) Show() {

	fmt.Println(pq.data)
	return
}
